#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include <algorithm>
#include <vector>
using namespace std;
typedef long long BigInteger;
//#include "biginteger.hpp"

vector<BigInteger> primes;

struct Pair {
    Pair(BigInteger t, BigInteger u) : t(t), u(u) {}
	BigInteger t;
	BigInteger u;
};

BigInteger quickpow(BigInteger a, BigInteger p) {
	if (p == 1) return a;
	if (p == 2) return a*a;
	BigInteger res = quickpow(a, p/2);
	return res*res*((p%2==1)?a:1);
}

Pair log_2(BigInteger n) {
	BigInteger t = 0;
	while (n%2==0) n = n / 2, t = t + 1;
	return Pair(t, n);
}

bool isprime(BigInteger p, BigInteger a) {
	Pair tu = log_2(p-1);
    printf("Checker: 2^%lld * %lld\n", tu.t, tu.u);
	BigInteger x = quickpow(a,tu.u)%p;
    printf("Making %lld\n", x);
	if (x == 1 || x == p-1) return true;
	while (tu.t != 0) {
		tu.t = tu.t - 1;
		x = (x*x)%p;
		if (x == p-1 || x == 1)
			return true;
	}
    return false;
}

bool Miller_Rabin(BigInteger p) {
	if (p == 2) return true;
	if (p < 2 || p%2==0) return false;

	BigInteger s = 1;
    printf("Miller Rabin %lld\t\t",p);
	for (BigInteger i = 0; i < s; i = i+1) {
		BigInteger a = primes[i];
		if (!isprime(p, a)) return false;
	}
	return true;
}

#define MAX_SIZE 10000

int main() {
	FILE* fptr = fopen(".prime", "r");
	/*char buffer[MAX_SIZE];
	while (fgets(buffer, MAX_SIZE, fptr) != NULL) {
		if (buffer[0] == '\0') continue;
		buffer[strlen(buffer)-1] = '\0';
		primes.push_back(BigInteger(buffer));
	}*/
    BigInteger bt;
    while (fscanf(fptr, "%lld", &bt) != EOF) primes.push_back(bt);
	fclose(fptr);

	for (BigInteger test = primes.back(), large = test * test; test <= large; test = test + 2)
		if (Miller_Rabin(test))
			primes.push_back(test), printf("%lld\n", test);
	
	fptr = fopen(".prime", "w");
	for (unsigned long i = 0; i<primes.size(); ++i) {
		fprintf(fptr, "%lld\n", primes[i]);
	}
	fclose(fptr);
	return 0;
}
